In the field of digital data communication, error-correcting circuitry, i.e. encoders and decoders, is used to achieve reliable communications on a system having a low signal-to-noise ratio (SNR). One example of an encoder is a convolutional encoder, which converts a series of data bits into a codeword based on a convolution of the input series with itself or with another signal. The codeword includes more data bits than are present in the original data stream. Typically, a code rate of ½ is employed, which means that the transmitted codeword has twice as many bits as the original data. This redundancy allows for error correction. Many systems also additionally utilize interleaving to minimize transmission errors.
The operation of the convolutional encoder and the MAP decoder are conveniently described using a trellis diagram which represents all of the possible states and the transition paths or branches between each state. During encoding, input of the information to be coded results in a transition between states and each transition is accompanied by the output of a group of encoded symbols. In the decoder, the original data bits are reconstructed using a maximum likelihood algorithm e.g. Viterbi Algorithm. The Viterbi Algorithm is a decoding technique that can be used to find the Maximum Likelihood path in the trellis. This is the most probable path with respect to the one described at transmission by the coder.
The basic concept of a Viterbi decoder is that it hypothesizes each of the possible states that the encoder could have been in and determines the probability that the encoder transitioned from each of those states to the next set of encoder states, given the information that was received. The probabilities are represented by quantities called metrics, of which there are two types: state metrics α (β for reverse iteration), and branch metrics γ. Generally, there are two possible states leading to every new state, i.e. the next bit is either a zero or a one. The decoder decides which is the most likely state by comparing the products of the branch metric and the state metric for each of the possible branches, and selects the branch representing the more likely of the two.
The Viterbi decoder maintains a record of the sequence of branches by which each state is most likely to have been reached. However, the complexity of the algorithm, which requires multiplication and exponentiations, makes the implementation thereof impractical. With the advent of the LOG-MAP algorithm implementation of the MAP decoder algorithm is simplified by replacing the multiplication with addition, and addition with a MAX operation in the LOG domain. Moreover, such decoders replace hard decision making (0 or 1) with soft decision making (Pk0 and Pk1). See U.S. Pat. No. 5,499,254 (Masao et al) and U.S. Pat. No. 5,406,570 (Berrou et al) for further details of Viterbi and LOG-MAP decoders. Attempts have been made to improve upon the original LOG-MAP decoder such as disclosed in U.S. Pat. No. 5,933,462 (Viterbi et al) and U.S. Pat. No. 5,846,946 (Nagayasu).
Recently turbo decoders have been developed. In the case of continuous data transmission, the data stream is packetized into blocks of N data bits. The turbo encode provides systematic data bits and includes first and second constituent convolutional recursive encoders respectively providing e1 and e2 outputs of codebits. The first encoder operates on the systematic data bits providing the e1 output of code bits. An encoder interleaver provides interleaved systematic data bits that are then fed into the second encoder. The second encoder operates on the interleaved data bits providing the e2 output of the code bits. The data uk and code bits e1 and e2 are concurrently processed and communicated in blocks of digital bits.
However, the standard turbo-decoder still has shortcomings that need to be resolved before the system can be effectively implemented. Typically, turbo decoders need at least 3 to 7 iterations, which means that the same forward and backward recursions will be repeated 3 to 7 times, each with updated branch metric values. Since a probability is always smaller than 1 and its log value is always smaller than 0, α, β and γ all have negative values. Moreover, every time γ is updated by adding a newly-calculated soft-decoder output after every iteration, it becomes an even smaller number. In fixed point representation too small a value of γ results in a loss of precision. Typically when 8 bits are used, the usable signal dynamic range is −255 to 0, while the total dynamic range is −255 to 255, i.e. half of the total dynamic range is wasted.
In a prior attempt to overcome this problem, the state metrics α and β have been normalized at each state by subtracting the maximum state metric value for that time. However, this method results in a time delay as the maximum value is determined. Current turbo-decoders also require a great deal of memory in which to store all of the forward and reverse state metrics before soft decision values can be calculated.
An object of the present invention is to overcome the shortcomings of the prior art by increasing the speed and precision of the turbo decoder while better utilizing the dynamic range, lowering the gate count and minimizing memory requirements.